#ifndef _BFS_HH_
#define _BFS_HH_
#include "common.hh"
#include "State.h"
#include "Torus.hh"
#include <queue>
#include <utility>
#include <set>


///
/// Breadth first Search generic template
///
/// Calls __action for each __valid_position in BFS order
///
struct bfs_node
{
	uLocation cell;
	int first_direction; // first direction in path used to come to current cell
	int last_direction;  // last direction  in path used to come to current cell
	unsigned depth;

	bfs_node(uLocation _loc, int _first_direction, int _last_direction, unsigned _depth) :
		cell(_loc), first_direction(_first_direction), last_direction(_last_direction), depth(_depth)
	{ }
};

template<typename _Action, typename _Condition>
void breadth_first_search(Map & map, uLocation sLoc, _Action & __action, _Condition & __valid_position)
{
        ants::visited.reset();
        std::queue<bfs_node> locQueue;
	locQueue.push(bfs_node(sLoc, -1, -1, 0));

	ants::visited.insert(sLoc);

	while(!locQueue.empty())
	{
		bfs_node node = locQueue.front();
		locQueue.pop();
		uLocation cLoc = node.cell;
		unsigned depth = node.depth;

		if(!__action(map,node)) return;

		for(int d=0; d<Map::TDIRECTIONS; d++)
		{
			uLocation nLoc = map.getLocation(cLoc, d);
			if(!ants::visited.count(nLoc) && __valid_position(map,sLoc,nLoc,depth))
			{
				if (depth)
					locQueue.push(bfs_node(nLoc, node.first_direction, d, depth+1));
				else
					locQueue.push(bfs_node(nLoc, d, d, depth+1));
			}
			ants::visited.insert(nLoc);
		}
	}
}

/// Functor for direct walking potentials
/// i.e. do not avoid dangerous positions
struct valid_for_walking_t
{
	unsigned distance;

	valid_for_walking_t(unsigned _distance) : distance(_distance) {}

	bool operator()(Map & map, uLocation sLoc, uLocation nLoc, unsigned depth)
	{
		return (!map[nLoc].isWater)&&(depth < distance);
	}
};


/// Functor for safe walking potentials
/// i.e. avoid dangerous positions
struct valid_for_safe_walking_t
{
	unsigned distance;

	valid_for_safe_walking_t(unsigned _distance) : distance(_distance) {}

	bool operator()(Map & map, uLocation sLoc, uLocation nLoc, unsigned depth)
	{
		return (!map[nLoc].isWater)&& map[nLoc].isSafe && (depth < distance);
	}
};


///
/// Walking BFS template
///
template<typename _Action>
void walk( Map & map, uLocation sLoc, unsigned distance, _Action & __action)
{
	valid_for_walking_t valid2walk(distance);
	breadth_first_search(map, sLoc, __action, valid2walk);
}


///
/// Safe Walking BFS template
///
template<typename _Action>
void safe_walk( Map & map, uLocation sLoc, unsigned distance, _Action & __action)
{
	valid_for_safe_walking_t valid4safe_walk(distance);
	breadth_first_search(map, sLoc, __action, valid4safe_walk);
}



#endif /* _BFS_HH_ */
